package leetcode;

public class GuessNumber {

	public static void main(String[] args) {
		GuessNumber object = new GuessNumber();
		for(int i = 6; i < 25; i++){
			System.out.println(i + " : " + object.getMoneyAmount2(i));
		}
	}
	
	public int getMoneyAmount(int n) {
		// 就是二分吧
		if (n <= 1) {
			return 0;
		}
		return getMoneyFromRange(1, n);
	}

	public int getMoneyFromRange(int left, int right) {
		if (left >= right) {
			return 0;
		}
		if (left + 1 == right) {
			return left;
		}
		if (left + 2 == right) {
			return left + 1;
		}
		if (left + 3 == right) {
			return left + 2 + left;
		}
		if (left + 4 == right) {
			return left + 1 + left + 3;
		}
		int middle;
		int res = 0;
		if (left < right) {
			middle = left + (right - left) / 2;
			int rightRange = getMoneyFromRange(middle + 1, right);
			int rightAddoneRange = getMoneyFromRange(middle + 2, right); 
			//后来我发现其实不对，比如1  2  3...15
			//选择的是12， 然后是12 + leftrange(1, 11) -> 18  = 30
			System.out.println("middle " + middle + " right: " + rightRange);
			System.out.println("middle " + (middle + 1) + " rightAddone: " + rightAddoneRange);
			res = Math.min(middle + rightRange, middle + 1 + rightAddoneRange);
		}
		return res;
	}
	
	
	//DP with memorization
	
	public int getMoneyAmount2(int n) {
        int[][] table = new int[n+1][n+1];
        return dp(table, 1, n);
    }
    
    private int dp(int[][] table, int left, int right){
        if(left >= right) return 0;
        if(table[left][right] != 0) return table[left][right];
		if (left + 1 == right) {
			return left;
		}
		if (left + 2 == right) {
			return left + 1;
		}
		if (left + 3 == right) {
			return left + 2 + left;
		}
		if (left + 4 == right) {
			return left + 1 + left + 3;
		}
        int res = Integer.MAX_VALUE;
        for(int x = right - 1; x >= left; x -= 2){
        	int leftRange = dp(table, left, x - 1);
			int rightRange = dp(table, x + 1, right);
			
            int tmp = x + Math.max(leftRange, rightRange);
            res = Math.min(res, tmp);
//            if(leftRange + 2 < rightRange){
//            	break;
//            }
        }
        table[left][right] = res;
        return res;
    }
}
